Evolution of Three-Dimensional Cellular Automata: Adaptive Culture Model

This paper is a continuation of work done in Evolution of Three-Dimensional Cellular Automata: Genetic Algorithms. See it for an explanation of cellular automata, the test problem in three-dimensional cellular automata configuration, and the representation of cellular automata configurations as genetic strings.

Emergent Collective Intelligence

Emergent Collective Intelligence is a new theory of how intelligence arises. It is based on diverse new research areas, including entomological studies of social insects, neurological studies of brain development, and sociological studies of human culture. It asserts that intelligent behavior (in ants, brains, cities, and eventually software [Johnson, 2001]) emerges from social interaction between simple agents. This theory forms a sharp contrast to classical psychology, philosophy, and Artificial Intelligence, with their strong emphasis on rational symbolic problem solving [Simon, 1996] and consciousness [Dennett, 1991].

In their research on the ants E. O. Wilson [Holldobler and Wilson, 1990] and later Deborah Gordon [Gordon, 1999] found that ant queens actually don't direct the work of the colony. The global behavior of the colony arises from the collective behavior of individual ants. Each is engaged in simple, fixed, nearly random behavior based purely on local stimulus. Wilson's research discovered the different pheromones (chemicals) emitted by ants. These are used to mark paths and otherwise influence the behavior of other ants in the colony. Gordon investigated how the simple, probabilistic behavior of individual ants resulted in efficient task allocation (foraging, nest repair, egg care, etc.) within the colony. Others have compared this to how old cities, which arose organically without central planning, often have superior and more humane layouts.

Scientists [Hofstadter, 1979] have also compared ant learning and behavior to the operations of neurons in the human brain. They have also evaluated neurons using sociological and evolutionary models:

Every brain cell in a newborn is a guess. If the spot to which it migrates and the function it adopts turn out to be necessities, it stays and even gains in "popularity" -- other cells massage it with nerve endings begging for what it has to give. If it is a motor neuron geared to make a tongue click like the African San language's popping "!" and everyone chattering 'round it pops away, it will grow vigorous and stay. If it's sandpapered by the baby talk of English burblers whose syllables never make their palates snap a "!", the cell prepared to make a tongue click will shrink, then die away. [Bloom, 2000, p. 130]

In Richard Dawkin's theory of memes ideas in the mind and their propagation via culture are compared to genes [Dawkins, 1976]. Memes compete for resources (mind-share), reproduce, and mutate. However, the theories of Evolutionary Collective Intelligence are not focused on the evolution of ideas, but of minds. They are concerned with how the behavior of an individual over a lifetime is altered by interactions with others. While in a genetic model change occurs when one generation is replaced by another, in a sociological model the same individuals persist and are influenced by neighbors to change. [Updated: the preceeding weak dismissal was taken from [Kennedy and Eberhart, 2001]. I suspect memes will be key; see [Blackmore, 1999] [Aunger, 2000][Aunger, 2002]]

Mind is social. We reject the cognitivistic perspective of mind as an internal, private thing or process and argue instead that both function and phenomenon derive from the interactions of individuals in a social world. Though it is mainstream social science, the statement needs to be made explicit in this age where the cognitivistic view dominates popular as well as scientific thought.

A. Human intelligence results from social interaction. Evaluating, comparing, and imitating one another, learning from experience and emulating the successful behaviors of others, people are able to adapt to complex environments through the discovery of relatively optimal patterns of attitudes, beliefs, and behaviors. Our species predilection for a certain kind of social interaction has resulted in the development of the inherent intelligence of humans.

B. Culture and cognition are inseparable consequences of human sociality. Culture emerges as individuals become more similar through mutual social learning. The sweep of culture moves individuals toward more adaptive patterns of thought and behavior. The emergent and immergent phenomena occur simultaneously and inseparably. [Kennedy and Eberhart, 2001, p. xx-xxi]

Adaptive Culture Model

The Adaptive Culture Model was published in 1997 by Robert Axelrod [see Kennedy and Eberhart, 2001, p. 263] as a model of the dissemination of culture. In this model the global fitness of a population rises as each individual interacts with its neighbors. The fitness of a random individual is compared to a random direct neighbor, and the less fit individual copies some feature from the more fit individual. Not only does the fitness of the less fit neighbors rise, but eventually the neighbor's fitness exceeds the previous best fitness. This occurs because good features are being copied from multiple fit neighbors, and features are being tried in new combinations. Eventually the fitness of the entire population rises.

The Adaptive Culture Model can also be used as an optimization algorithm, the same as genetic algorithms. My simulation run used a 10 by 10 grid of individuals. Each individual was represented by a 54-bit string. Each string was randomly initialized. An individual was chosen at random, as was a direct neighbor (above, below, left, or right). Their fitness was compared, and the one with lower fitness copied one bit at random from the more fit individual into the corresponding location in its bitstring.

Here is a grid of fitness scores: highest score = 1568 average score = 149

548000003949781472439
-249-1450000117701471748
-131-18000-17713721079012721274
-129-1392400-18013711078117500
-271-30400015681272127400
-300-33300-2141471-803127800
0-2370-12657421470137515700
0-268-1992-78-80107812761765880
624329-89-65001276107613730
592-1836-1300-8000127465814701374

Here is the grid of fitness scores, 20,000 iterations later: highest score = 2155 average score = 1657

1373146314741274166620581865196318641569
1866175716691373205818611470206218651695
17321745-2211960215519611762147015671743
1730166701471205818611763166618621733
1664166701764176317621764166317651477
1567137110791566186117621861186217661569
166715668811599182920581961206020601568
1764166414701371186118631766176818651765
1667166314721272166619631865196219621668
1669160812771278166918651962186419601570

Note the Adaptive Culture Model itself also forms a cellular automaton. Each individual (cell) is updated based on purely local interactions and identical rules. It currently differs from a true cellular automaton in that cells are randomly chosen for evaluation, instead of uniformly updating the entire grid on each time step. It should be possible to instead run the algorithm in true cellular automata fashion. Cellular automata evolving cellular automata... [Updated: also note the similarity to genetic algorithms. ACM copies a single random bit from a more fit neighbor, while genetic algorithms essentially copy half the bits from a reproductive partner (also chosen based on fitness). ACM's purely local interactions may also more closely model actual natural selection than the global reproduction found in simple genetic algorithm implementations (like mine).]

Results

The test problem is the two-valued three-dimensional cellular automata using the new evaluation function from Evolution of Three-Dimensional Cellular Automata: Genetic Algorithms. The genotypes are identical, and a "generation" consists of 100 iterations. This way the amount of calculation is comparable to the genetic algorithm version, which also performed 100 fitness calculations in each generation for its population size of 100. The Adaptive Culture Model was able to solve the cellular automata configuration problem in 1,010 generations. This compares to 126 generations for the genetic algorithm.

Conclusion

The Adaptive Culture Model can be used to successfully evolve cellular automata configurations. At present it appears genetic algorithms are a more efficient technique for performing this evolution. The primary topic of Swarm Intelligence [Kennedy and Eberhart, 2001] is the similar but more advanced Particle Swarm algorithm. It incorporates additional velocity terms (similar to the momentum terms used in backpropagation neural network training) and should produce much faster evolution. A next step is to implement the Particle Swarm algorithm.

References

Aunger, Robert, ed., 2000. Darwinizing Culture: The Status of Memetics as a Science.

Aunger, Robert, 2002. The Electric Meme: A New Theory of How We Think.

Blackmore, Susan, 1999. The Meme Machine.

Bloom, Howard, 2000. Global Brain: The Evolution of Mass Mind From the Big Bang to the 21st Century.

Dawkins, Richard, 1976. The Selfish Gene.

Dennett, Daniel C., 1991. Consciousness Explained.

Gordon, Deborah, 1999. Ants at Work: How an Insect Society is Organized.

Hofstadter, Douglas R., 1979. Godel, Escher, Bach: an Eternal Golden Braid.

Holldobler, Bert and E. O. Wilson, 1990. The Ants.

Johnson, Steven, 2001. Emergence: The Connected Lives of Ants, Brains, Cities, and Software.

Kennedy, James and Russell C Eberhart, 2001. Swarm Intelligence.

Simon, Herbert A., 1996. The Sciences of the Artificial.